#!/usr/bin/python
# Filename: HuffmanTree.py

# Huffman Tree

from BTree import *
from Heap import *


class HuffmanTreeNode(BTreeNode):
    '''Huffman Tree Node, inherit from BTreeNode'''
    def __init__(self, value, left=None, right=None):
        '''value must be tuple (value, weight)'''
        BTreeNode.__init__(self, value, left, right)

    def __cmp__(self, other):
        return self.value[1] - other.value[1]

class HuffmanTree(BTree):
    '''Huffman Tree is a Binary Tree'''
    def __init__(self):
        BTree.__init__(self)
        self.table = []

    def build_tree(self, l):
        if len(l) < 2: return False
        list = [HuffmanTreeNode(i) for i in l]
        min_heap = MinHeap()
        min_heap.build_heap(list)
        while min_heap.size > 1:
            # in this algo, using MinHeap.set_root(value) to reduce a sift_up()
            # or else, using two remove_min() and a insert(value) is also ok
            node1 = min_heap.remove_min()
            node2 = min_heap.min()
            node = HuffmanTreeNode((None, node1.value[1]+node2.value[1]))
            node.left = node1
            node.right = node2
            min_heap.set_root(node)
        self.root = min_heap.remove_min()
        del min_heap
        del list
        self.build_table()
        return True

    def build_table(self):
        seq = ""

        def add_to_table(node, seq):
            if not node.left and not node.right:
            # here, use == None compare will cause error.
            # bcz a built-in cmp function is defined for HuffmanTreeNode.
            # to compare node.value[0] == None is another solution
                self.table.append((node.value[0], seq))
            else:
                seql = seq + "0"
                add_to_table(node.left, seql)
                seqr = seq + "1"
                add_to_table(node.right, seqr)

        add_to_table(self.root, seq)

    def decode(self, string):
        pass


if __name__ == "__main__":

    def test_of_huffman_tree_node():
        n1 = HuffmanTreeNode((10, 1))
        n2 = HuffmanTreeNode((1, 2))
        print n1
        print n2
        print "n1 > n2 ?:", n1 > n2

    def test_of_huffman_tree():
        l1 = [('E', 34), ('U', 9), ('D', 10), ('L', 8), ('C', 4), ('F', 2), ('Z', 1), ('K', 1)]
        l2 = [(0, 2), (1, 3), (2, 5), (3, 7), (4, 19), (5, 23),
            (6, 17), (7, 19), (8, 23), (9, 29), (10, 31), (11, 19), (12, 23)]
        h1 = HuffmanTree()
        h1.build_tree(l1)
        #print_tree_indented(h1.root)
        #inorder(h1.root)
        for i in h1.table:
            print i,
    
    #test_of_huffman_tree_node()
    test_of_huffman_tree()
